#include <iostream>
#include <queue>

#include "common/utils.hpp"

TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
    // 都为null的情况也会进入这个分支
    if (root1 == nullptr) return root2;
    if (root2 == nullptr) return root1;

    std::queue<TreeNode*> que;

    que.push(root1);
    que.push(root2);

    while(!que.empty()) {
        TreeNode* node1 = que.front();
        que.pop();
        TreeNode* node2 = que.front();
        que.pop();

        // 两个节点不为空
        node1->val += node2->val;

        // 左节点都不为null
        if (node1->left != nullptr && node2->left != nullptr) {
            que.push(node1->left);
            que.push(node2->left);
        }

        // 右节点都不为null
        if (node1->right != nullptr && node2->right != nullptr) {
            que.push(node1->right);
            que.push(node2->right);
        }

        // node1左节点为空，node2左节点不为空
        if (node1->left == nullptr && node2->left != nullptr) {
            node1->left = node2->left;
        }

        // node1右节点为空，node2右节点不为空
        if (node1->right == nullptr && node2->right != nullptr) {
            node1->right = node2->right;
        }

        // 底下两种情况不需要处理，因为最后返回的是root1
        // if (node1->left != nullptr && node2->left == nullptr) {
            
        // }
        // if (node1->right != nullptr && node2->right == nullptr) {
            
        // }
    }

    return root1;
}

extern TreeNode* commonRoot;

int main() {
    std::vector<int> num1 = { 1, 3, 2, 5 };
    std::vector<int> num2 = { 2, 1, 3, -1, 4, -1, 7 };
    TreeNode* node1 = createTreeNodeByArray(num1);
    printTreeNode(node1);
    std::cout << "=================\n";
    TreeNode* node2 = createTreeNodeByArray(num2);
    printTreeNode(node2);
    std::cout << "=================\n";
    TreeNode* ret = mergeTrees(node1, node2);
    printTreeNode(ret);
}